/*
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
*/
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <utility>

using namespace std;

class Solution {
public:
    void solve(vector<vector<string>>& board) {
        int x_len=board.size();
        int y_len=board[0].size();
        vector<vector<bool>> visited(x_len,vector<bool>(y_len,false));
        vector<vector<int>> direction{{1,0},{-1,0},{0,1},{0,-1}};
        stack<pair<int,int>> dfs;
        pair<int,int> tmp;
        vector<pair<int,int>> pos;
        bool find_next=false;
        bool can_modify=true;

        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                if(board[i][j]=="O"&&!visited[i][j]){
                    pos.clear();
                    can_modify=true;
                    dfs.push(make_pair(i,j));
                    pos.push_back(make_pair(i,j));
                    visited[i][j]=true;
                    cout<<"("<<i<<","<<j<<") :"<<board[i][j]<<endl;
                    while(!dfs.empty()){
                        cout<<"1"<<endl;
                        tmp=dfs.top();
                        find_next=false;
                        for(auto& dir:direction){
                            int new_x=tmp.first+dir[0];
                            int new_y=tmp.second+dir[1];
                            if(0<=new_x&&new_x<x_len&&0<=new_y&&new_y<y_len&&board[new_x][new_y]=="O"&&!visited[new_x][new_y]){
                                cout<<"("<<i<<","<<j<<") :"<<board[i][j]<<endl;
                                visited[new_x][new_y]=true;
                                dfs.push(make_pair(new_x,new_y));
                                pos.push_back(make_pair(new_x,new_y));
                                find_next=true;
                                if(new_x==0||new_x==x_len-1||new_y==0||new_y==y_len-1){
                                    can_modify=false;
                                }
                            }
                        }
                        if(!find_next){
                            dfs.pop();
                        }
                    }   
                    if(!pos.empty()&&can_modify){
                        cout<<"2"<<endl;
                        for(int k=0;k<pos.size();k++){
                            board[pos[k].first][pos[k].second]="X";
                        }
                    }
                }
            }
        }
    }
};

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int x_len=board.size();
        if(x_len==0){
            return;
        }
        int y_len=board[0].size();
        vector<vector<bool>> visited(x_len,vector<bool>(y_len,false));
        vector<vector<int>> direction{{1,0},{-1,0},{0,1},{0,-1}};
        stack<pair<int,int>> dfs;
        pair<int,int> tmp;
        vector<pair<int,int>> pos;
        bool find_next=false;
        bool can_modify=true;

        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                if(board[i][j]=='O'&&!visited[i][j]){
                    pos.clear();
                    can_modify=true;
                    dfs.push(make_pair(i,j));
                    pos.push_back(make_pair(i,j));
                    if(i==0||i==x_len-1||j==0||j==y_len-1){
                        can_modify=false;
                    }
                    visited[i][j]=true;
                    while(!dfs.empty()){
                        tmp=dfs.top();
                        find_next=false;
                        for(auto& dir:direction){
                            int new_x=tmp.first+dir[0];
                            int new_y=tmp.second+dir[1];
                            if(0<=new_x&&new_x<x_len&&0<=new_y&&new_y<y_len&&board[new_x][new_y]=='O'&&!visited[new_x][new_y]){
                                visited[new_x][new_y]=true;
                                dfs.push(make_pair(new_x,new_y));
                                pos.push_back(make_pair(new_x,new_y));
                                find_next=true;
                                if(new_x==0||new_x==x_len-1||new_y==0||new_y==y_len-1){
                                    can_modify=false;
                                }
                            }
                        }
                        if(!find_next){
                            dfs.pop();
                        }
                    }   
                    
                    if(!pos.empty()&&can_modify){
                        for(int k=0;k<pos.size();k++){
                            board[pos[k].first][pos[k].second]='X';
                        }
                    }
                }
            }
        }
    }
};

//2020.6.20 dfs+边界寻找O点及其连通O点
class Solution {
public:
    void solve(vector<vector<char>>& board) {

        if(board.empty()){
            return;
        }
        //记录是否访问过
        vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));
        //记录是否真的需要替换，边界O点及其连通的O点是不需要替换的，在dfs中对边界O点及其连通的O点置为false
        vector<vector<bool>> O2X(board.size(),vector<bool>(board[0].size(),true));
        for(int i=0;i<board[0].size();i++){
            dfs(board,0,i,visited,O2X);
        }
        for(int i=0;i<board[0].size();i++){
            dfs(board,board.size()-1,i,visited,O2X);
        }
        for(int i=0;i<board.size();i++){
            dfs(board,i,0,visited,O2X);
        }
        for(int i=0;i<board.size();i++){
            dfs(board,i,board[0].size()-1,visited,O2X);
        }
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(board[i][j]=='O'&&O2X[i][j]){
                    board[i][j]='X';
                }
            }
        }
    }
private:
    vector<vector<int>> dir{{1,0},{-1,0},{0,1},{0,-1}};
    void dfs(vector<vector<char>>& board,int i,int j,vector<vector<bool>>& visited,vector<vector<bool>>& O2X){
        if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]=='X'||visited[i][j]){
            return;
        }
        visited[i][j]=true;
        O2X[i][j]=false;//边界O点及其连通O点不需要替换
        for(auto& d:dir){
            dfs(board,i+d[0],j+d[1],visited,O2X);
        }
    }
};

int main(){
    Solution s;
    vector<vector<string>> in{{"X","X","X","X"},{"X","O","O","X"},{"X","X","O","X"},{"X","O","X","X"}};
    s.solve(in);
    return 0;
}